package week_03;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 示例 1：
 * <p>
 * 输入：numCourses = 2, prerequisites = [[1,0]]
 * 输出：true
 * 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
 * 示例 2：
 * <p>
 * 输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
 * 输出：false
 * 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/course-schedule
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 **/
public class CoursesCanFinish_207 {
    private int n;
    private int[][] prerequisites;
    private List<List<Integer>> edges;
    private int[] indegs;
    private List<Integer> orders;


    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //  使用广度优先 搜索 每个点广度搜索一遍
        //  每个点计算一个入度，出一个点则将下一个点的入度减1
        //建图 加边 建立入度数组
        n = numCourses;
        prerequisites = prerequisites;
        orders = new ArrayList<>();
        edges = new ArrayList<>();
        indegs=new int[n];
        for (int i = 0; i < n; i++) {
            edges.add(new ArrayList<>());
        }
        for (int[] item : prerequisites) {
            int u = item[0];
            int v = item[1];
            addEdge(u, v);
        }

        // 拓扑排序计算
        topSort();
        return orders.size()==n;
    }

    public void topSort() {
        Deque<Integer> queue = new LinkedList<>();
        // 0度入队列
        for (int i = 0; i < n; i++) {
            if (indegs[i] == 0) queue.offer(i);
        }
        // topSort
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            orders.add(cur);
            for (int e : edges.get(cur)) {
                indegs[e] -= 1;
                if (indegs[e] == 0) {
                    queue.offer(e);
                }
            }
        }
    }

    public void addEdge(int u, int v) {
        edges.get(u).add(v);
        indegs[v] += 1;
    }


}
